package 热题100.动态规划.杨辉三角_118_简单;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:
输入: numRows = 1
输出: [[1]]

提示:
1 <= numRows <= 30

思路：
    每一步都和之前的有关—----动态规划
    先确定f[i][j]的含义：  位置i，j的值是多少
    确定状态转移公式：      通过观察怎么运算的能看出，当前值等于上一层，相对的两个位置的值相加。
    初始化                 外侧的值都是1
    确定遍历顺序           与上一层相关，则正序

* */
public class Solution {
    public static void main(String[] args) {
            List<List<Integer>>  ans = generate(5);
            for (List<Integer> p : ans){
                for (int q : p){
                    System.out.println(q);
                }
            }
    }
    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();
        // 动态规划数组
        Integer[][] f = new Integer[numRows][];
        // 数组初始化
        for (int i = 0; i < numRows; i ++){
            f[i] = new Integer[i + 1];
            f[i][0] = f[i][i] = 1;
        }
        // 状态转移公式
        for (int i = 2; i < numRows; i ++){
            for (int j = 1; j < i; j ++){
               f[i][j] = f[i - 1][j - 1] + f[i - 1][j];
            }
        }
        // 将数组转换为链表
        for (int i = 0; i < numRows; i ++){
            ans.add(Arrays.asList(f[i]));
        }
        return ans;
    }
}
